Sublinear function

A sublinear function, in linear algebra and related areas of mathematics, is a function $f: V \rightarrow \mathbf{F}$ on a vector space V over F, an ordered field (e.g. the real numbers $\mathbb{R}$ ), which satisfies

$f(\gamma x ) = \gamma f\left( x\right)$ for any $\gamma\in \mathbb{R}_%2B$ and any x ∈ V (positive homogenity),

$f(x %2B y) \le f(x) %2B f(y)$ for any x, y ∈ V (subadditivity).

In functional analysis the name Banach functional is used for sublinear function, especially when formulating Hahn–Banach theorem.

In computer science, a function $f: \mathbb{Z^%2B} \rightarrow \mathbb{R}$ is called sublinear if $f(n) \in o(n)$ in asymptotic notation (Notice the small $\,o$ ). Formally, $f(n) \in o(n)$ if and only if, for any given $\,c > 0$ , there exists an $\,n_0$ such that^[1]

$n \geq n_0 \Rightarrow 0 \leq f(n) < c \cdot n$

This means that for any linear function $f'\,$ , for sufficiently large input $f\,$ grows slower than $f'\,$ .

1 Examples
2 Properties
3 Operators
4 References

Examples

Every (semi-)norm is a sublinear function. Opposite is not true, because (semi-)norms can have their domain vector space over any field (not necessarily ordered) and must have $\mathbb{R}$ as their codomain.

Properties

Every sublinear function is a convex functional.

Operators

The concept can be extended to operators that are homogeneous and subadditive. This requires only that the codomain be, say, an ordered vector space to make sense of the conditions.

References

^ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (2001) [1990]. "3.1". Introduction to Algorithms (2nd edition ed.). MIT Press and McGraw-Hill. pp. 47–48. ISBN 0-262-03293-7.

Sublinear function

Contents

Examples

Properties

Operators

References